package com.zhn;

import java.util.ArrayList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 */


//如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
public class GenerateParenthesis {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        backTracking(new StringBuilder(),0,0,n);
        return res;
    }

    public void backTracking(StringBuilder cur,int open,int close,int max){
        if(cur.length() == max * 2){
            res.add(cur.toString());
            return;
        }
        if(open < max){
            cur.append('(');
            backTracking(cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if(close < open){
            cur.append(')');
            backTracking(cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}
